package com.base.dynamicprograming;

import java.util.HashMap;

/**
 * TODO(413. 等差数列划分)
 *
 * @author leon
 * @date 2021年12月07日 19:56
 */
public class NumberOfArithmeticSlices {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if(nums == null||n<3){
            return 0;
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(2,0);
        map.put(1,0);
        int cha=nums[1] - nums[0];
        int start = 0;
        int res = 0;
        int end =2;
        for(;end<n;end++){
            // 不存在差

            if(cha != nums[end] - nums[end-1]){

                res +=map.get(end-start);
                start = end-1;
            }else{
                int tmp = 2*map.get(end-start)+1-map.get(end-start-1);
                map.put(end-start+1,tmp);
            }
            cha = nums[end] - nums[end-1];
        }
        res +=  map.get(end-start);
        return res;
    }

    /**
     * 增量法
     *
     * 这道题主要是需要找到其规律,从小的例子出发,仔细观察,会发现当整个数组为(1, 2, 3, 4, 5, 6)的时候,我们先取出前三个,
     * (1, 2, 3)的等差数列的个数为1,(1, 2, 3, 4)的等差数列的个数为3,(1, 2, 3, 4, 5)的等差数列的个数为6,(1, 2, 3, 4, 5, 6)的
     * 等差数列个数为10,以此类推我们可以很容易的发现在一个等差数列中加入一个数字,如果还保持着等差数列的特性,每次的增量都会加1,如果刚加进来的
     * 数字与原先的序列构不成等差数列,就将增量置为0,接下来继续循环,执行以上的逻辑即可
     *
     * @param nums
     * @return
     */
    public int numberOfArithmeticSlices1(int[] nums) {
        int n = nums.length;
        if(nums == null||n<3){
            return 0;
        }
        int res = 0;
        int add = 0;
        for(int end = 1;end<n-1;end++){
            if(nums[end]-nums[end-1]==nums[end+1]-nums[end]){
                res += ++add;
            }else{
                add = 0;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new NumberOfArithmeticSlices().numberOfArithmeticSlices(new int[]{1,1,3,4,5,6}));
    }
}
